# -*- coding: utf-8 -*-

"""单链表中环的检测：
快慢指针，看两个指针是否相遇"""

def solution(ls):
    slow = ls.head.next
    fast = slow

    try:
        while True:
            slow, fast = slow.next, fast.next.next
            if not fast.next:
                print('该链表中无环')
                break
            elif fast is slow:
                print('该链表中有环')
                break
    except AttributeError:
        print('该链表中无环')


if __name__ == '__main__':
    from classic.linkedlist import SingleLinkedList
    ls = SingleLinkedList(0,1,2,3,4,5,6,7,8,9)
    solution(ls)

    n = 3
    p, x = ls.head.next, 0
    while True:
        if not p.next:
            break
        if x == n:
            pr = p
        x, p = x+1, p.next
    p.next = pr

    solution(ls)
